/*
 * @lc app=leetcode.cn id=106 lang=cpp
 *
 * [106] 从中序与后序遍历序列构造二叉树
 *
 * https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/
 *
 * algorithms
 * Medium (72.36%)
 * Likes:    727
 * Dislikes: 0
 * Total Accepted:    187.2K
 * Total Submissions: 258.7K
 * Testcase Example:  '[9,3,15,20,7]\n[9,15,7,20,3]'
 *
 * 给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder
 * 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
 * 
 * 
 * 
 * 示例 1:
 * 
 * 
 * 输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
 * 输出：[3,9,20,null,null,15,7]
 * 
 * 
 * 示例 2:
 * 
 * 
 * 输入：inorder = [-1], postorder = [-1]
 * 输出：[-1]
 * 
 * 
 * 
 * 
 * 提示:
 * 
 * 
 * 1 <= inorder.length <= 3000
 * postorder.length == inorder.length
 * -3000 <= inorder[i], postorder[i] <= 3000
 * inorder 和 postorder 都由 不同 的值组成
 * postorder 中每一个值都在 inorder 中
 * inorder 保证是树的中序遍历
 * postorder 保证是树的后序遍历
 * 
 * 
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
   TreeNode* traversal(vector<int>& inorder, int inorderBegin, int inorderEnd, vector<int>& postorder, int postorderBegin, int postorderEnd){
        if(postorderBegin == postorderEnd) return NULL;
        int rootval = postorder[postorderEnd-1]; 
        TreeNode* root = new TreeNode(rootval);

        if (postorderEnd - postorderBegin == 1) return root;

        //确定根在中序数组中的位置
        int rootvalInorderIndex;
        for(rootvalInorderIndex = inorderBegin; rootvalInorderIndex < inorderEnd; rootvalInorderIndex++){
            if(inorder[rootvalInorderIndex] == rootval) break;
        }

        //开始分割
        //分割中序序列左边
        int inorderLeftBegin = inorderBegin;
        int inorderLeftEnd = rootvalInorderIndex;
        //分割中序序列右边
        int inorderRightBegin = rootvalInorderIndex + 1;
        int inorderRightEnd = inorderEnd;

        //分割后序序列左边
        int postorderLeftBegin = postorderBegin;
        int postorderLeftEnd = postorderBegin + rootvalInorderIndex - inorderLeftBegin;
        //分割后序序列右边
        int postorderRightBegin = postorderBegin + rootvalInorderIndex - inorderLeftBegin;
        int postorderRightEnd = postorderEnd - 1;

        //开始递归
        root->left = traversal(inorder, inorderLeftBegin, inorderLeftEnd, postorder, postorderLeftBegin, postorderLeftEnd);
        root->right = traversal(inorder, inorderRightBegin, inorderRightEnd, postorder, postorderRightBegin, postorderRightEnd);

        return root; 
    }
    
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if(inorder.size() == 0 || postorder.size() == 0) return NULL;
        return  traversal(inorder, 0, inorder.size(), postorder, 0, postorder.size());
    }

    // //定义新的vector
    // TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
    //     if(inorder.size() == 0) return NULL;
    //     int rootVal = postorder[postorder.size()-1];
    //     TreeNode* root = new TreeNode(rootVal);

    //     //确定根元素在中序的位置
    //     int rootValInorderIndex = 0;
    //     for(int i = 0; i < inorder.size(); i++){
    //         if(inorder[i] == rootVal) {
    //             rootValInorderIndex = i;
    //             break;
    //         }
    //     }

    //     //分割中序
    //     vector<int> inorderLeft(inorder.begin(), inorder.begin()+rootValInorderIndex);
    //     vector<int> inorderRight(inorder.begin()+rootValInorderIndex+1, inorder.end());

    //     //中序左数组的长度
    //     int size = inorderLeft.size();

    //     //分割后序
    //     vector<int> postorderLeft(postorder.begin(), postorder.begin()+size);
    //     vector<int> postorderRight(postorder.begin()+size, postorder.end()-1);

    //     root->left = buildTree(inorderLeft, postorderLeft);
    //     root->right = buildTree(inorderRight, postorderRight);

    //     return root;



    //     // if(postorder.size() == 0) return NULL;
    //     // int rootVal = postorder[postorder.size() - 1];
    //     // TreeNode* root = new TreeNode(rootVal);


    //     // // 叶子节点
    //     // if (postorder.size() == 1) return root;

    //     // //找出在中序遍历中的坐标
    //     // int valInorderIndex;
    //     // for(int i = 0; i < inorder.size(); i++){
    //     //     if(inorder[i] == rootVal) {
    //     //         valInorderIndex = i;
    //     //         break;
    //     //     }
    //     // }


    //     // //开始分割中序序列-左闭右开
    //     // vector<int> inorderLeft(inorder.begin(), inorder.begin() + valInorderIndex);
    //     // vector<int> inorderright(inorder.begin()+valInorderIndex+1, inorder.end());

    //     // int inorderLeftSize = inorderLeft.size();

    //     // //开始分割后序序列-左闭右开
    //     // vector<int> postorderLeft(postorder.begin(), postorder.begin() + inorderLeftSize);
    //     // vector<int> postorderRight(postorder.begin() + inorderLeftSize, postorder.end() - 1);

    //     // //开始递归， 分别链上左右两边
    //     // root->left = buildTree(inorderLeft, postorderLeft);
    //     // root->right = buildTree(inorderright, postorderRight);

    //     // return root;
    // }

};
// @lc code=end

